package exercise;

import java.util.*;

// 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列
// https://leetcode.cn/problems/permutations-ii/
public class L230630_II {
//    public List<List<Integer>> permuteUnique(int[] nums) {
//        int len = nums.length;
//        List<List<Integer>> ans = new ArrayList<>();
//        boolean[] used = new boolean[len];
//        List<Integer> path = new ArrayList<>();
//        Set<String> set = new HashSet<>();
//
//        dfs(nums, len, ans, used, path, 0, set);
//        return ans;
//    }
//
//    /**
//     * @param nums  原数组
//     * @param len   原数组的长度
//     * @param ans   存放最终的答案
//     * @param used  这个数是否被 path 使用过
//     * @param path  临时存放并且符合条件的单个答案
//     * @param depth 这个数组的深度
//     */
//    private void dfs(int[] nums, int len, List<List<Integer>> ans, boolean[] used,
//                     List<Integer> path, int depth, Set<String> set) {
//        if (depth == len) {
//            StringBuilder stringBuilder = new StringBuilder();
//            for (Integer x : path) {
//                stringBuilder.append(x);
//            }
//            if (!set.contains(stringBuilder.toString())) {
//                ans.add(new ArrayList<>(path));
//                set.add(stringBuilder.toString());
//            }
//            return;
//        }
//
//        for (int i = 0; i < nums.length; i++) {
//            if (!used[i]) {
//                used[i] = true;
//                path.add(nums[i]);
//
//                dfs(nums, len, ans, used, path, depth + 1, set);
//
//                // 回溯
//                path.remove(path.size() - 1);
//                used[i] = false;
//            }
//        }
//    }

    public List<List<Integer>> permuteUnique(int[] nums) {
        int len = nums.length;
        List<List<Integer>> ans = new ArrayList<>();
        boolean[] used = new boolean[len];
        List<Integer> path = new ArrayList<>();
        Arrays.sort(nums);

        dfs(nums, len, ans, used, path, 0);
        return ans;
    }

    /**
     * @param nums  原数组
     * @param len   原数组的长度
     * @param ans   存放最终的答案
     * @param used  这个数是否被 path 使用过
     * @param path  临时存放并且符合条件的单个答案
     * @param depth 这个数组的深度
     */
    private void dfs(int[] nums, int len, List<List<Integer>> ans, boolean[] used,
                     List<Integer> path, int depth) {
        if (depth == len) {
            ans.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (!used[i]) {
                if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) {
                    continue;
                }
                used[i] = true;
                path.add(nums[i]);

                dfs(nums, len, ans, used, path, depth + 1);

                // 回溯
                path.remove(path.size() - 1);
                used[i] = false;
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 2};
        L230630_II solution = new L230630_II();
        List<List<Integer>> lists = solution.permuteUnique(nums);
        System.out.println(lists);
    }
}
